package com.xxy.tree.threadedbinarytree;

import jdk.nashorn.internal.runtime.regexp.joni.EncodingHelper;

/**
 * @author xxy
 * @create 2021 1 24 14:53
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        HeroNode root = new HeroNode(1,"tom");
        HeroNode node2 = new HeroNode(3,"jack");
        HeroNode node3 = new HeroNode(6,"smith");
        HeroNode node4 = new HeroNode(8,"mary");
        HeroNode node5 = new HeroNode(10,"king");
        HeroNode node6 = new HeroNode(14,"dim");

        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        ThreadBinaryTree threadedBinaryTree = new ThreadBinaryTree();
        threadedBinaryTree.setRoot(root);
        threadedBinaryTree.threadNodes(root);
        //10号节点的
        System.out.println(node5.getLeft());
    }
}
//一棵二叉树
//定义一棵线索化二叉树
class ThreadBinaryTree{
    private HeroNode root;//根节点

    //为了实现线索化，需要给指向当前节点的前驱结点的指针
    //在递归进行线索化的时候，pre总是指向前一个节点
    private HeroNode pre=null;
    public void setRoot(HeroNode root) {
        this.root = root;
    }
    /**
     * 编写对二叉树进行中序线索化的方法
     */
    public void threadNodes(HeroNode node){
        if (node==null){
            return;
        }
        //1.先线索化左子树
        threadNodes(node.getLeft());
        //2.再线索化当前节点
        //处理当前节点的的前驱结点
        if(node.getLeft()==null){
            //让当前节点的左指针指向前驱结点
            node.setLeft(pre);
            //修改当前节点的左指针类型
            node.setLeftType(1);
        }
        //处理后继节点
        if(pre!=null&&pre.getRight()==null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        //每处理一个节点后，让当前节点是下一个节点的前驱结点
        pre=node;
        //3.在线索化右子树
        threadNodes(node.getRight());
    }

    /**
     * 遍历线索化二叉树
     */
    public void threadedList(){
        HeroNode node = root;
        while (node!=null){
            //循环的找到leftType ==1的节点
            //后面随着遍历而变化，因为当leftType ==1时，说明该节点是按照线索化
            //处理后的有效节点
            while (node.getLeftType()==0){
                node = node.getLeft();
            }
            //打印当前这个节点
            System.out.println(node);
            //如果当前节点的右指针指向的后继节点，就一直输出
            while (node.getRightType()==1){
                node = node.getRight();
                System.out.println(node);
            }
            //替换这个遍历的节点
            node = node.getRight();
        }
    }
    //前序遍历
    public  void preOrder(){
        if(this.root!=null){
            this.root.preOrder();
        }else {
            System.out.println("当前二叉树为空");
        }
    }
    //中序遍历
    public void midOrder(){
        if(this.root!=null){
            this.root.midOrder();
        }else {
            System.out.println("当前二叉树为空！");
        }
    }
    //后序遍历
    public void postOrder(){
        if(this.root!=null){
            this.root.postOrder();
        }else {
            System.out.println("当前二叉树为空！");
        }
    }
    //前序查找
    public HeroNode preOrderSearch(int no){
        if(this.root!=null){
            return this.root.preOrderSearch(no);
        }else{
            return null;
        }
    }
    //中序查找
    public HeroNode midOrderSearch(int no){
        if(this.root!=null){
            return this.root.midOrderSearch(no);
        }else{
            return null;
        }
    }
    // 后序查找
    public HeroNode postOrderSearch(int no){
        if(this.root!=null){
            return this.root.postOrderSearch(no);
        }else{
            return null;
        }
    }
    //删除节点
    public void delNode(int no){
        if(root!=null){
            if(root.getNumber()==no){
                root=null;
            }else {
                root.delNode(no);
            }
        }else{
            System.out.println("空树！");
        }
    }
}
//创建HeroNode节点
class HeroNode{
    private int number;
    private String name;
    private HeroNode left;//左节点
    private HeroNode right;//右节点
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }
    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }
    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    //说明：如果leftType ==0,表示指向的是左子树，如果是1表示指向前驱结点
    //然后rightType就是类似的
    public HeroNode(int number,String name){
        this.name=name;
        this.number = number;
    }
    //提供get和set方法
    public int getNumber() {
        return number;
    }

    public void setNumber(int number) {
        this.number = number;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "number=" + number +
                ", name='" + name + '\'' +
                '}';
    }
    //删除节点
    /*
        1.因为我们的二叉树是单向的，所以我们是判断当前节点的子节点是否为需要
        删除的节点，而不是判断当前节点。
     */
    public  void delNode(int no){
        if(this.left!=null&&this.left.number==no){
            this.left=null;
            return;
        }
        if(this.right!=null&&this.right.number==no){
            this.right=null;
            return;
        }
        if(this.left!=null){
            this.left.delNode(no);
        }
        if(this.right!=null){
            this.right.delNode(no);
        }
    }
    //前序遍历
    public void preOrder(){
        //输出当前节点
        System.out.println(this);
        //左子树
        if(this.left!=null){
            this.left.preOrder();
        }
        //左子树遍历结束，回到了根节点，然后开始右节点
        if(this.right!=null){
            this.right.preOrder();
        }
        //结束
    }
    //中序遍历
    public void midOrder(){
        //首先遍历左子树
        if(this.left!=null){
            this.left.midOrder();
        }
        //输出父节点
        System.out.println(this);
        //遍历右节点
        if(this.right!=null){
            this.right.midOrder();
        }
        //结束
    }
    //后序遍历
    public void postOrder(){
        //先遍历左子树
        if(this.left!=null){
            this.left.preOrder();
        }
        //遍历右子树
        if(this.right!=null){
            this.right.postOrder();
        }
        //输出节点
        System.out.println(this);
    }
    //前序查找
    public HeroNode preOrderSearch(int no){
        if(this.number ==no){
            return this;
        }
        //进行左子树
       HeroNode resNode =null;
        if (this.left != null){
            resNode = this.left.preOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        //右子树
        if(this.right!=null){
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }
    //中序查找
    public HeroNode midOrderSearch(int no){
        //进行左子树
        HeroNode resNode =null;
        if (this.left != null){
            resNode = this.left.preOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        if(this.number ==no){
            return this;
        }
        //右子树
        if(this.right!=null){
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }
    //后序查找
    public HeroNode postOrderSearch(int no) {
        //进行左子树
       HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //右子树
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        if(resNode!=null){
            return resNode;
        }
        System.out.println("进入后序查找~");
        if (this.number == no) {
            return this;
        }
        return null;
    }
}
